package org.example;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Test2 {
    //leetcode 139 单词拆分 https://leetcode.cn/problems/word-break/description/
    public boolean wordBreak(String s, List<String> wordDict) {
        int m = wordDict.size(), n = s.length();
        //dp数组表示s.substring(0,i)之间的字符串是否呢个够由wordDict中的单词组成
        boolean[] dp = new boolean[n+1];
        Set<String> set = new HashSet<>(wordDict);
        dp[0] = true;
        s = " " + s;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j>= 1; j--) {
                String word = s.substring(j,i+1);
                if (dp[j-1] && set.contains(word)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        String s = "leetcode";
        List<String> list = Arrays.asList("leet","code");
        test2.wordBreak(s,list);
        System.out.println(666);
    }
}
